#ifndef __DYNAMICARRAY_H_
#define __DYNAMICARRAY_H_

#include<cstddef>//size_t头文件
#include<iostream>
#include<climits>
namespace DARRAY
{
    using ElementType = void *;//引入类型别名  //void *
    class DynamicArray
    {
    public:
        DynamicArray();
        DynamicArray(const DynamicArray& a);
        DynamicArray& operator=(const DynamicArray& a);
        ~DynamicArray();

        void SetFreeFunc(void (*Free)(void *))
        {
            this->Free = Free;
        }

        void SetPrintFunc(void (*Print)(void *))
        {
            this->Print = Print;
        }

        void SetCompareFunc(bool (*Compare)(void *, void *))
        {
            this->Compare = Compare;
        }
        
        void SetGreaterFunc(bool (*Greater)(void *, void *))
        {
            this->Greater = Greater;
        }

        void SetCopyDataFunc(ElementType (*CopyData)(void *))
        {
            this->CopyData = CopyData;
        }

        //插入
        //尾插法
        void InsertTail(const ElementType & element);
        //头插法
        void InsertHead(const ElementType & element);
        //中间插入
        void InsertIndex(const ElementType & element, size_t index);

        //删除
        //按位置删除
        void RemoveByIndex(size_t index);
        //按值删除
        void RemoveByElement(const ElementType & element);

        //查找
        //按位置查找
        ElementType* FindByIndex(size_t index);//因为常规的数据类型无法判断下标是否合法，因此需要返回指针
        //按值查找
        //返回下标的集合
        DynamicArray FindByElement(const ElementType& element);

        //修改
        //按位置修改
        void UpdataByIndex(size_t index, const ElementType & newValue);
        //按数值修改
        void UpdataByElement(const ElementType & oldValue, const ElementType & newValue);

        ElementType& operator[](int index);//统一查找和修改 //O(1)

        //排序算法
        void Sort();

        //去重算法
        void Duplicate();

        //合并算法:两个有序数列合并成一个新的有序数列
        DynamicArray Merge(const DynamicArray& a);

        //取交集
        DynamicArray FdIntrSctn(const DynamicArray & a);

        //取并集
        DynamicArray FdUnionSet(const DynamicArray & a);

        //取差集
        DynamicArray FindDifference(const DynamicArray & a);

        //判断两个数列数组是否相等
        bool operator==(const DynamicArray & a); 

        //二分查找  没找到返回ULONG_MAX
        size_t BinarySearch(const ElementType & element);

        //查找子序列
        bool Contains(const DynamicArray & a);

        //查找连续子序列
        bool ContnsContains(const DynamicArray & a);

        //获取子序列
        DynamicArray SubSquence(size_t index,size_t len);

        void show();
    private:
        //分组函数
        size_t partition(size_t start, size_t end);
        void FastSort(size_t start, size_t end,size_t CurDepth,size_t MaxDepth);
        void InsertSort(size_t start, size_t end);
        void ReSize(size_t capacity);
        ElementType * array;
        size_t capacity;
        size_t size;

        void (*Free)(void *);   //释放对象
        bool (*Compare)(void *, void *);    //比较大小
        void (*Print)(void *);  //打印
        bool (*Greater)(void *, void *);    //大于
        ElementType (*CopyData)(void *);
    };
}

#endif